package com.learning;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BSTTree {
	protected BSTNode root;

	public BSTTree() {
		root = null;
	}

	protected void visit(BSTNode p) {
		System.out.println(p.key + " ");

	}

	/**
	 * search anh insert node in BST Tree
	 * 
	 * @param el
	 */
	public void insert(int el) {
		BSTNode p = root, prev = null;
		while (p != null) {
			prev = p;
			if (el < p.key) {
				p = p.leftNode;
			} else {
				p = p.rightNode;
			}
		}
		if (root == null) // tree is empty;
			root = new BSTNode(el);
		else if (el < prev.key)
			prev.leftNode = new BSTNode(el);
		else
			prev.rightNode = new BSTNode(el);

	}

	/**
	 * print tree LNR
	 * 
	 * @param p
	 */
	protected void inorder(BSTNode p) {
		if (p != null) {
			visit(p);
			inorder(p.leftNode);
			inorder(p.rightNode);
		}
	}

	/**
	 * NLR non recursive
	 * 
	 * @param p
	 */
	protected void inorderNonRecursive() {
		System.out.println("------");
		BSTNode p1 = root;
		Queue<BSTNode> queue = new LinkedList<BSTNode>();
		if (p1 != null) {
			queue.add(p1);
			while (!queue.isEmpty()) {
				p1 = queue.remove();
				visit(p1);
				if (p1.leftNode != null)
					queue.add(p1.leftNode);
				if (p1.rightNode != null)
					queue.add(p1.rightNode);
			}
		}
	}

	/**
	 * count num node in tree
	 * 
	 */
	int num = 0;

	public int count(BSTNode p) {
		if (p != null) {
			count(p.leftNode);
			num++;
			count(p.rightNode);
		}
		return num;
	}

	/**
	 * count num non recursive
	 */
	int numNonRecursive = 0;

	public int countNonRecursive(BSTNode p) {
		Queue<BSTNode> bstNodes = new LinkedList<BSTNode>();
		BSTNode temp = p;
		if (p != null) {
			bstNodes.add(p);
			while (!bstNodes.isEmpty()) {
				temp = bstNodes.remove();
				numNonRecursive++;
				if (temp.leftNode != null)
					bstNodes.add(temp.leftNode);
				if (temp.rightNode != null)
					bstNodes.add(temp.rightNode);
			}
		}
		return numNonRecursive;
	}

	/**
	 * search value
	 */
	public boolean search(int key, BSTNode p) {
		// boolean check=false;
		if (p != null) {
			if (p.key == key) {
				return true;
			} else {
				search(key, p.leftNode);
				if (p.key == key) {
					return true;
				}
				inorder(p.rightNode);
			}
		}
		return false;
	}

	/**
	 * using stack print LRN
	 */
	public void printNRL() {
		BSTNode p = root, q = root;
		Stack<BSTNode> nodeStack = new Stack<BSTNode>();
		while (p != null) {
			for (; p.leftNode != null; p = p.leftNode)
				nodeStack.push(p);
			while (p != null && (p.rightNode == null || p.rightNode == q)) {
				visit(p);
				q = p;
				if (nodeStack.isEmpty())
					return;
				p = nodeStack.pop();
			}
			nodeStack.push(p);
			p = p.rightNode;
		}
	}

	/**
	 * LNR
	 */
	public void iterativeInorder() {
		BSTNode p = root;
		Stack<BSTNode> travStack = new Stack<BSTNode>();
		while (p != null) {
			while (p != null) { // stack the right child (if any)
				if (p.rightNode != null) // and the node itself when going
					travStack.push(p.rightNode); // to the left;
				travStack.push(p);
				p = p.leftNode;
			}
			p = (BSTNode) travStack.pop();// pop a node with no left child
			while (!travStack.isEmpty() && p.rightNode == null) {// visit it and
																	// all
				visit(p); // nodes with no right child;
				p = (BSTNode) travStack.pop();
			}
			visit(p); // visit also the first node with
			if (!travStack.isEmpty()) // a right child (if any);
				p = (BSTNode) travStack.pop();
			else
				p = null;
		}
	}

	/**
	 * use to delete node in the BST tree
	 */
	public boolean deleteNode(int key) {
		BSTNode p = root, prev = null;
		BSTNode node, tmp;
		while (p != null && p.key != key) {
			prev = p;
			if (p.key < key)
				p = p.rightNode;
			else
				p = p.leftNode;
		}
		node = p;
		if (p != null && p.key == key) {
			if (node.leftNode == null)
				node = node.rightNode;
			else if (node.rightNode == null)
				node = node.leftNode;
			else {
				tmp = prev.leftNode;
				while (tmp.rightNode != null)
					tmp = tmp.rightNode;
				tmp.rightNode = node.rightNode;
				node = node.leftNode;
			}
			if (p == root)
				root = node;
			else if (prev.leftNode == p)
				prev.leftNode = node;
			else
				prev.rightNode = node;
			return true;
		}
		return false;
	}

	/**
	 * find max in BSTTree
	 */
	int max;

	public int findMax(BSTNode parent) {
		BSTNode p = parent;
		if (p != null)
			if (p.rightNode != null)
				findMax(p.rightNode);
			else if (p.leftNode != null)
				findMax(p.leftNode);
			else
				max = p.key;
		return max;
	}

}
